package com.markedquilt.SwordForOffer;
/*
 * PackageName: com.markedquilt.SwordForOffer
 * ClassName:   _maxValue
 * Author:   zhang
 * Date:     Created in 2020/11/3
 * Description:
 * History:
 * <author>        <time>             <version>          <desc>
 * 作者姓名         修改时间            版本号              描述
 * zhang           2020/11/3      1.0
 */

/**
 * Title:
 * Project: LeetcodeProblem
 *  示例 1:
 *
 *  输入:
 * [
 *   [1,3,1],
 *   [1,5,1],
 *   [4,2,1]
 * ]
 * 输出: 12
 * 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
 * @author ZhangKe
 * Created on 2020/11/3
 */
public class _maxValue47 {
    public static int maxValue(int[][] grid) {
        for (int j = 1; j < grid[0].length; j++) {
            grid[0][j]+=grid[0][j-1];
        }
        for (int i = 1; i < grid.length; i++) {
            grid[i][0]+=grid[i-1][0];
        }
        for (int i = 1; i < grid.length; i++) {
            for (int j = 1; j < grid[0].length; j++) {
                grid[i][j] += Math.max(grid[i-1][j],grid[i][j-1]);
            }
        }

        return grid[grid.length-1][grid[0].length-1];
    }

    public static void main(String[] args) {
        int[][] array = {{1,2,5},{3,2,1}};
        System.out.println(maxValue(array));
    }
}
// {1,3,1},
// {1,5,1},
// {4,2,1}
//dp[i+j] = max(dp[i+j-1],dp[i-1+j])
//dp[2] = arr[0][0]

//145
//2910
//61112